/*
题目描述：数组中只出现一次的两个数字
方法：
先考虑数组中只出现一次的一个数字问题
每个数异或自己得到 0
将每个数异或起来最后得到的那个数就是出现一次的数
回到这个问题，只需要将两个只出现一次的数字分到两个组里，在对每个组进行上面的处理
 */
public class E56_1 {
    public static void main(String[] args) {
        int[] array = {2,4,3,6,3,2,5,5};
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        FindNumsAppearOnce(array, num1,num2);
        System.out.println(num1[0] + " " + num2[0]);
    }

    public static void FindNumsAppearOnce(int [] array,int[] num1 , int[] num2) {
        if(array == null || array.length <= 0){
            return;
        }
        int resultExclusiveOR = 0;//表示只出现一次的两个数字异或的结果
        for(int i = 0; i < array.length; i++){
            resultExclusiveOR ^= array[i];
        }
        int indexOf1 = FindFirstBitIs1(resultExclusiveOR);//根据两个数字以后结果，划分两个组
        num1[0] = num2[0] = 0;
        for(int j = 0; j < array.length; j++){
            if(IsBit1(array[j], indexOf1)){//特定位置上为 1 的一组进行异或
                num1[0] ^= array[j];
            }
            else{
                num2[0] ^= array[j];
            }
        }
    }
    //找到 num 二进制表示中最右边为 1 的位置
    public static int FindFirstBitIs1(int num){
        int indexBit = 0;
        while((num & 1 ) == 0 && indexBit < 32){
            num = num >> 1;
            indexBit++;
        }
        return indexBit;
    }
    //用来判断 num 右边第indexBit为是否为 1
    public static boolean IsBit1(int num, int indexBit){
        num = num >> indexBit;
        return (num & 1) > 0;
    }
}
